import java.util.*;

/**
 * 面试题 04.03. 特定深度节点链表
 * https://leetcode-cn.com/problems/list-of-depth-lcci/
 */
public class Solutions_mianshi_04_03 {
    public static void main(String[] args) {
        String str = "[1 2 3 4 5 # 7 8]";
        TreeNode tree = MyTreeNodeUtils.deserialize(str);
        ListNode[] result = listOfDepth(tree);
        System.out.println(result);
    }

    public static ListNode[] listOfDepth(TreeNode tree) {
        // 队列实现广度优先搜索
        Queue<TreeNode> queue = new LinkedList<>();
        List<ListNode> res = new ArrayList<>();
        ListNode head = null, cur = null;
        // 添加根节点
        queue.add(tree);
        while (!queue.isEmpty()) {
            head = new ListNode(-1);
            cur = head;
            int size = queue.size();
            // size 即是该层的节点个数
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                cur.next = new ListNode(node.val);
                cur = cur.next;
                // 左右子节点不为 null 时，入队
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(head.next);
        }
        // list 列表转换为数组
        return res.toArray(new ListNode[res.size()]);
    }
}
